import java.util.Arrays;

/**
 * 面试题66：构建乘积数组
 * <p>
 * 同 LeetCode 238. 除自身以外数组的乘积
 */
public class Offer_66 {
    /**
     * 优化方法一的空间复杂度
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] constructArr(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }
        int[] ans = new int[len];

        // 第一次遍历时，ans[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 0 的元素左侧没有元素，所以 ans[0] = 1
        ans[0] = 1;
        for (int i = 1; i < len; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        // 第二次遍历
        // right 为右侧所有元素乘积
        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 ans[i]，右边的乘积为 right
            ans[i] = ans[i] * right;
            // right 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 right 上
            right *= nums[i];
        }
        return ans;
    }

    /**
     * 方法一：左右乘积列表
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int[] constructArr1(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }

        // left 和 right 分别表示左右两侧的乘积列表
        int[] left = new int[len];
        int[] right = new int[len];

        // left[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 0 的元素，因为左侧没有元素，所以 left[0] = 1
        left[0] = 1;
        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        // right[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 len-1 的元素，因为右侧没有元素，所以 right[len-1] = 1
        right[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        Offer_66 solution = new Offer_66();
        int[] nums = { 1, 2, 3, 4, 5 };
        int[] ans = solution.constructArr1(nums);
        System.out.println(Arrays.toString(ans));
    }
}
